package com.huang.leetcode.tree;

import com.huang.leetcode.constant.TreeNode;

/**
 * @Author：CreateSequence
 * @Date：2020-08-05 21:30
 * @Description：将有序数组转换为二叉搜索树
 * 题解：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-24/
 */
public class PB108 {

    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return null;
        }
        return bst(nums, 0, nums.length);
    }

    private TreeNode bst(int[] nums, int left, int right) {

        /**
         * 从根节点节点开始向左右构建二叉树，
         * 从数组找到中点，然后将将数组分为中点前和中点后两段，第一次为找到树的根节点，继续向下递归时为找到某两个子节点的父节点。
         * 可以理解为先构建以根节点为父节点的树，接着然后向左右递归构建子树。
         */

        if (left > right) {
            return null;
        }
        //获取中点(这个写法是避免大数相加导致溢出)
        int mid = left + (right - left ) / 2;
        //构建一个父节点
        TreeNode root = new TreeNode(nums[mid]);
        //向左右递归构建子树
        root.left = bst(nums, left, mid);
        root.right = bst(nums, mid, right);

        return root;
    }

}
